The invention relates generally to the field of digital computers and more specifically to functional units for processing predetermined types of instructions. The invention particularly provides a circuit or functional unit for use in connection with execution of various types of instructions for rearranging bits of a data word.
Computers process data in accordance with instructions. A number of types of instructions rearrange bits of data words in predetermined patterns by, for example, shifting them, rotating them and the like. Typically, such instructions have two operands, with one operand comprising the data word and the other operand providing control information indicating in part how the bits of the data word are to be rearranged. In some cases, all of the bits of the data word are used in the rearranged data word. In other cases, some or all of the bits of the data word are discarded and replaced with bits having predetermined values, such as xe2x80x9czeroxe2x80x9d or xe2x80x9cone.xe2x80x9d
Typical examples of such instructions are xe2x80x9cunsigned shift left,xe2x80x9d xe2x80x9cunsigned shift right,xe2x80x9d xe2x80x9carithmetic shift right,xe2x80x9d xe2x80x9crotate left,xe2x80x9d and xe2x80x9crotate right.xe2x80x9d If the operand data word consists of xe2x80x9cNxe2x80x9d bits D0 D1 D2 . . . DNxe2x88x921 (generally Dn) and xe2x80x9cmxe2x80x9d is a control operand having a value 0xe2x89xa6m less than N, an unsigned shift left instruction results in a shift of the bits of the operand data word to the left by xe2x80x9cmxe2x80x9d places, with the bits in the xe2x80x9cmxe2x80x9d bit positions at the right end of the rearranged data word being provided with bits having the value xe2x80x9czero.xe2x80x9d That is, the rearranged data word would be Dm Dm+1 . . . DNxe2x88x921 0 . . . 0, where the xe2x80x9cmxe2x80x9d bit positions at the right are provided with bits having the value xe2x80x9czero,xe2x80x9d and the bits D0 . . . Dmxe2x88x921 of the operand data word are xe2x80x9cshifted outxe2x80x9d of the left end of the rearranged data word. Essentially, the bit in bit position xe2x80x9ckxe2x80x9d of the rearranged data word receives the bit in bit position k+m of the operand data word for k+m less than N, and otherwise the bit in the rearranged data word receives the value xe2x80x9czero.xe2x80x9d Similarly, an unsigned shift right instruction results in a shift of the bits of the operand data word to the right by xe2x80x9cmxe2x80x9d places, with the bits in the xe2x80x9cmxe2x80x9d bit positions at the left end of the rearranged data word being provided with bits having the value xe2x80x9czero.xe2x80x9d That is, the rearranged data word would be 0 . . . 0 D0 D1 . . . DNxe2x88x921xe2x88x92m, where the xe2x80x9cmxe2x80x9d bit positions to the left are provided with bits having the value xe2x80x9czeroxe2x80x9d and the bits DNxe2x88x92m . . . DNxe2x88x921 of the operand data word are xe2x80x9cshifted outxe2x80x9d of the right end of rearranged data word. Essentially, the bit in bit position xe2x80x9ckxe2x80x9d of the rearranged data word receives the bit in bit position kxe2x88x92m of the operand data word, for kxe2x88x92mxe2x89xa70, and otherwise the bit in the rearranged data word receives the value xe2x80x9czero.xe2x80x9d It will be appreciated that, if xe2x80x9cmxe2x80x9d has the value xe2x80x9czero,xe2x80x9d the rearranged data word is the same as the input data word for both types of instructions.
An arithmetic shift right instruction provides a result similar to the unsigned shift right, except that, instead of providing the xe2x80x9cmxe2x80x9d bit positions at the left end of the rearranged data word with the value xe2x80x9czero,xe2x80x9d they are provided with bits having the value in bit position D0 of the operand data word. That is, the rearranged data word is D0 . . . D0 D0 D1 . . . DNxe2x88x921xe2x88x92m, where there are xe2x80x9cmxe2x80x9d bits D0 . . . D0 to the left of bits D0 D1 . . . DNxe2x88x921xe2x88x92m. The arithmetic shift right instruction is typically used with an operand data word which is a signed number, with the D0 data bit comprising the sign, that is, indicating whether the number is positive or negative, and the remaining bits D1 . . . DNxe2x88x921 indicating the absolute value of the number. The arithmetic shift right instruction results in the bits D1 . . . DNxe2x88x921 comprising the absolute value being shifted to the right by xe2x80x9cmxe2x80x9d bit positions, with the bits DNxe2x88x92m . . . DNxe2x88x921 being shifted out of the rearranged data word, and the sign bit D0 being extended through the first m+1 bit positions of the rearranged data word.
The rotate left and rotate right instructions are also similar to the unsighted shift left and unsigned shift right instructions, except that, instead of providing bits having the value xe2x80x9czeroxe2x80x9d in the xe2x80x9cinxe2x80x9d bit positions of the left and right end of the rearranged data word, respectively, the bits that are xe2x80x9cshifted outxe2x80x9d of the right and left ends respectively are xe2x80x9cshifted intoxe2x80x9d those xe2x80x9cmxe2x80x9d bit positions. That is, the rearranged data word provided in response to the rotate left and rotate right instructions would be Dm Dm+1 . . . DNxe2x88x921 D0 . . . Dmxe2x88x921 and DNxe2x88x92m . . . DNxe2x88x921 D0 D1 . . . DNxe2x88x921xe2x88x92m, respectively. Essentially, for a rotate left instruction, the bit in bit position xe2x80x9ckxe2x80x9d of the rearranged data word receives the value of the bit in bit position k+m of the operand data word for k+m less than N, and otherwise bit xe2x80x9ckxe2x80x9d of the rearranged data word receives the bit in bit position k+mxe2x88x92N of the operand data word. Similarly, for a rotate right instruction, the bit in bit position xe2x80x9ckxe2x80x9d of the rearranged data word receives the bit in bit position kxe2x88x92m of the operand data word for kxe2x88x92m greater than 0, and otherwise bit xe2x80x9ckxe2x80x9d of the rearranged data word receives the bit in bit position kxe2x88x92m+N of the operand data word.
Several other types of bit manipulation instructions have also been proposed, such as, for example, a generalized bit reverse instruction and a generalized shuffle/unshuffle instruction. For a generalized bit reverse instruction bit xe2x80x9ckxe2x80x9d in the rearranged data word receives the bit in bit position k XOR m of the operand data word. For example, if xe2x80x9cmxe2x80x9d equals xe2x80x9cone,xe2x80x9d the rearranged data word is D1 D0 D3 D2 D5 D4 . . . DNxe2x88x921 DNxe2x88x922, with successive pairs of bits in bit positions Dn Dn+1 of the operand data word being reversed Dn+1 Dn in the rearranged data word. On the other hand, if xe2x80x9cmxe2x80x9d equals xe2x80x9ctwo,xe2x80x9d the rearranged data word is D2 D3 D0 D1 D6 D7 D4 D5 . . . . DNxe2x88x922 DNxe2x88x921 DNxe2x88x924 Dxe2x88x923, with successive pairs of pairs of bits in bit positions Dn Dn+1 Dn+2 Dn+3 of the operand data word being reversed Dn+2 Dn+3 Dn Dn+1 in the rearranged data word. Generally, if xe2x80x9cmxe2x80x9d is equal to xe2x80x9cpxe2x88x92q,xe2x80x9d where xe2x80x9cpxe2x80x9d and xe2x80x9cqxe2x80x9d are both powers of two, the generalized bit reverse instruction results in a division of the operand data word into sections of size xe2x80x9cpxe2x80x9d and each section being divided into chunks of size xe2x80x9cqxe2x80x9d, with the sections in the rearranged data word being in the same order as in the operand data word, but the chunks in each section being in reversed order in the rearranged data word. This is illustrated in the above examples, since for m=1=2xe2x88x921 (=21xe2x88x9220), the size of each section was two and the size of each chunk was one, and successive pairs of bits in bit positions Dn Dn+1 of the operand data word were reversed Dn+1 Dn in the rearranged data word. Similarly, for m=2=4xe2x88x922 (=22xe2x88x9221), the size of each section was four and the size of each chunk was two, and successive pairs of pairs of bits in bit positions Dn Dn+1 Dn+2 Dn+3 of the operand data word were reversed Dn+2 Dn+3 Dn Dn+1 in the rearranged data word. If, for example, m=7=8xe2x88x921 (=23xe2x88x9220), the generalized bit reverse instruction results in a rearranged data word in which the bit positions of the bits in each of the operand data word are in reversed order. On the other hand, if m=Nxe2x88x928 (=2LogNxe2x88x9223) (where, it will be assumed, Log2N is an integer), the generalized bit reverse instruction results in a rearranged data word in which the order of bytes in the operand data word is reversed in the rearranged data word. If m=0, the rearranged data word corresponds to the operand data word.
The operation enabled by a generalized shuffle/unshuffle instruction is somewhat more complex. To xe2x80x9cshufflexe2x80x9d xe2x80x9cNxe2x80x9d items, such as bits of an operand data word, is to rearrange them so that the xe2x80x9cn-thxe2x80x9d item of the rearranged data word corresponds to item (2*(n mod (N/2))+((2n/N) mod 2) of the operand data word. The inverse is the xe2x80x9cunshufflexe2x80x9d operation, in which item xe2x80x9cnxe2x80x9d of the rearranged data word corresponds to item ((nxe2x88x92(n mod 2))/2)+((n mod 2)*(N/2)).
The invention provides a new and improved system, comprising a circuit or functional unit for use in connection with execution of various types of instructions for rearranging bits of a data word. The functional selectively performs a number of types of bit rearrangement operations, including a generalized bit reverse operation and a generalized shuffle/unshuffle operation, and in addition can left and right unsigned shift operations and an arithmetic shift right operation. The functional unit includes a shifter array and a control signal generator. The shifter array includes a plurality of selector circuits arrayed in a number of stages for shifting bits of an input data word in accordance with control signals, the output of the last stage corresponding to a rearranged output data word. The control signal generator generates control signals in response to rearrangement operation type and pattern information.